package org.dyndns.opendemogroup.optimizer;

import java.util.Random;

/**
 * Based on slide 7 of <code>howGAsWork1.pdf</code>.
 */
public class GenericGenerationalGeneticAlgorithm
{
	// { private fields

	private final int maximumRuns;

	private final int maximumGenerations;

	private final int maximumEvaluations;
	
	private final long[] runSeeds;

	private final int populationSize;

	private final IOptimizationProblem problem;

	private final int memberSize;

	private final ISelection selection;

	private final IOperation[] operations;

	private final double fitnessTarget;

	private final double fitnessTolerance;

	private Random randomSource;

	private final OptimizationEventSink event;

	// }

	// TODO: Add a constructor that also takes a random seed

	public GenericGenerationalGeneticAlgorithm ( OptimizationProfile profile )
	{
		// { initialize
		maximumRuns = profile.MaximumRuns;
		maximumGenerations = profile.MaximumGenerations;
		maximumEvaluations =
			( 0 == profile.MaximumEvaluations ) ? profile.MaximumGenerations
					* profile.PopulationSize : profile.MaximumEvaluations;
		runSeeds = profile.RunSeeds;
		populationSize = profile.PopulationSize;
		problem = profile.Problem;
		memberSize = problem.getMemberSize ( );
		selection = profile.Selection;
		operations = profile.Operations;
		fitnessTarget = profile.FitnessTarget;
		fitnessTolerance = profile.FitnessTolerance;
		event = new OptimizationEventSink ( this );
		// }
	}

	public static void execute ( OptimizationProfile profile )
	{
		GenericGenerationalGeneticAlgorithm ggga =
			new GenericGenerationalGeneticAlgorithm ( profile );
		ggga.execute ( );
	}

	/**
	 * Attempts to solve the optimization problem by performing the specified
	 * number of runs on random populations.
	 * 
	 * @return An array of RunResult instances, representing the results of all
	 *         runs.
	 */
	public RunResult[] execute ( )
	{
		Population population = createPopulation ( );

		RunResult[] results = new RunResult[maximumRuns];
		for ( int run = 0; run < maximumRuns; run++ )
		{
			event.startRun ( run );

			randomSource = new Random ( runSeeds[run % runSeeds.length] );
			population.initializeRandomPopulation ( randomSource, problem );
			RunResult result = run ( population );
			results[run] = result;

			event.finishRun ( result );
		}

		return results;
	}

	public Population createPopulation ( )
	{
		Population result = new Population ( populationSize, memberSize );
		return result;
	}

	/**
	 * Executes the GGGA for a single run through generations until the fitness
	 * target is met, the number of generations is exceeded or the number of
	 * fitness evaluations is met.
	 * 
	 * @return The best member of the run.
	 */
	public RunResult run ( Population population )
	{
		RunResult result = new RunResult ( );
		Population nextPopulation = createPopulation ( );
		population.computeFitnesses ( problem, randomSource );
		population.sort ( );

		int gen, numberOfEvaluations = 0;
		Member bestMember = null;
		for ( gen = 0; gen < maximumGenerations; gen++ )
		{
			event.startGeneration ( gen );

			// { perform pairs of operations
			event.startOperations ( );
			selection.reset ( randomSource, population, problem );
			// TODO: break up this loop into separate loops for each
			// operation, since we don't need the operations to take place
			// in any particular order or to use up random numbers for this
			// ...EXCEPT if SlidingBias is involved!
			for ( int i = 0; i < populationSize; i += 2 )
			{
				Member parentOne, parentTwo, childOne, childTwo;
				// { select two individuals
				Pair<Member, Member> selectedPair =
					selection.select ( randomSource, population, problem, i );

				parentOne = selectedPair.first;
				parentTwo = selectedPair.second;

				childOne = nextPopulation.members[i];
				childTwo = nextPopulation.members[i + 1];
				// }
				// select and perform genetic operation
				// TODO: de-hardcode this equal probability distribution
				// TODO: make probability distribution adaptive
				// TODO: make probability distribution predictable
				int operation = randomSource.nextInt ( operations.length );
				event.performOperation ( i );
				operations[operation].perform ( randomSource, problem, parentOne,
					parentTwo, childOne, childTwo );
			}
			event.finishOperations ( );
			// }

			// { swap population and nextPopulation
			// TODO: Nested use depends on results being based on the Population
			// instance provided, but this swapping introduces the possibility
			// that an odd number of generations will have the results based on
			// the temporary population.  This could potentially be avoided by
			// performing a swap/copy when the bad conditions are identified.
			Population temp = population;
			population = nextPopulation;
			nextPopulation = temp;
			// }

			// { compute fitnesses
			event.startFitnessComputations ( );
			// TODO: report "performFitnessComputation"
			population.computeFitnesses ( problem, randomSource );
			event.finishFitnessComputations ( );
			// }

			// { sort population
			numberOfEvaluations += populationSize;
			event.startPopulationSort ( );
			population.sort ( );
			event.finishPopulationSort ( );
			// }

			// { have we satisfied the termination condition for this run?
			bestMember = population.getBestMember ( problem );

			// { check if bestMember is good enough
			double bestFitness = bestMember.getFitness ( );
			boolean goodEnough = false;
			if ( problem.isMaximizing ( ) )
			{
				goodEnough = ( bestFitness >= fitnessTarget );
				if ( !goodEnough && fitnessTolerance > 0.0 )
				{
					goodEnough =
						areApproximatelyEqual ( bestFitness, fitnessTarget,
							fitnessTolerance );
				}
			}
			else
			{
				goodEnough = ( bestFitness <= fitnessTarget );
				if ( !goodEnough && fitnessTolerance > 0.0 )
				{
					goodEnough =
						areApproximatelyEqual ( bestFitness, fitnessTarget,
							fitnessTolerance );
				}
			}
			// }

			event.finishGeneration ( bestMember );
			if ( goodEnough || numberOfEvaluations > maximumEvaluations )
			{
				// designate result for run
				break;
			}
			// }
		}
		// { prepare result
		result.Update ( population, problem.isMaximizing ( ) );
		result.NumberOfGenerations = gen;
		result.NumberOfEvaluations = numberOfEvaluations;
		try
		{
			result.BestMember = (Member) bestMember.clone ( );
		}
		catch ( CloneNotSupportedException cnse )
		{
			assert false : "Umm... I implemented .clone on Member; "
					+ "this should NOT happen!";
		}
		// }
		return result;
	}

	public static boolean areApproximatelyEqual ( double one, double two,
			double delta )
	{
		if ( delta <= 0.0 )
		{
			throw new IllegalArgumentException (
				"'delta' must be greater than 0.0" );
		}
		boolean result = ( Math.abs ( one - two ) < delta );
		return result;
	}

	/**
	 * @return Allows engine users to sign up for events.
	 */
	public OptimizationEventSink getEventSink ( )
	{
		return event;
	}

	public Random getRandomSource ( )
	{
		return randomSource;
	}

	public void setRandomSource ( Random randomSource )
	{
		this.randomSource = randomSource;
	}
}
